980D - Perfect Groups - CodeForces Solution

#include <bits/stdc++.h>
#define int long long
#define just return
#define monika 0
#define inc(i) (++ (i))
#define dec(i) (-- (i))
#define Rep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i <= i##Limit ; inc(i))
#define Dep(i, a, b) for(register int i = (a) , i##Limit = (b) ; i >= i##Limit ; dec(i))

using namespace std;

const int maxn = 200010, mod = 1e9 + 7;
int n, tot = 0;
int a[maxn], k[maxn], h[maxn], ans[maxn] = {0};
bool vis[maxn];
bool f;

int read() {
  int x=0,w=1;char ch=0;
  while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
  return x*w;
}

void init() {
    Rep(i, 1, tot) vis[i] = 0;
    vis[0] = 1;
}

signed main() {
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif

    n = read();
    Rep(i, 1, n) {
        a[i] = read();
        if(a[i] == 0) {
            h[i] = 0;
            continue;
        }
        f = 0;
        Rep(j, 1, tot) {
            if(a[i] * k[j] < 0) continue;
            int x = sqrt(a[i] * k[j]);
            if(x * x == a[i] * k[j]) {
                h[i] = j;
                f = 1; break;
            }
        }
        if(!f) {
            k[++ tot] = a[i];
            h[i] = tot;
        }
    }
    Rep(i, 1, n) {
        init();
        int cnt = 0;
        Rep(j, i, n) {
            if(!vis[h[j]]) {
                vis[h[j]] = 1;
                cnt ++;
            }
            ans[cnt] ++;
        }
    }
    printf("%lld", ans[0] + ans[1]);
    Rep(i, 2, n) printf(" %lld", ans[i]);

	just monika;
}